﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

class Sol1094
{


    public bool CarPooling2(int[][] trips,int capacity)//自己想的模拟法，
    {
        Dictionary<int,int> map = new Dictionary<int,int>();//记录在每站上车或者下车的人数

        int len=trips.Length;
        int end = 0;//记录终点的车站
        for (int i = 0; i < len; i++)
        {
            end=Math.Max(end, trips[i][1]);
            if (!map.ContainsKey(trips[i][1])){


                map[trips[i][1]] = trips[i][0];//上车人数

            }
            else//之前的trip有上车的
            {
                map[trips[i][1]] += trips[i][0];
            }


            if (!map.ContainsKey(trips[i][2]))
            {


                map[trips[i][2]] = -trips[i][0];//下车人数

            }
            else
            {
                map[trips[i][2]] -= trips[i][0];
            }
            end = Math.Max(end, trips[i][2]);



        }

        int curPeople = 0;
        for(int i = 0; i <= end;i++)//遍历所有的车站
        {
            if (map.ContainsKey(i))//说明有上或者下车的
            {
                curPeople += map[i];

                if(curPeople > capacity)
                {
                    return false;
                }

            }


        }
        return true;
    }
    public bool CarPooling(int[][] trips, int capacity)//差分法
    {
        Dictionary<int, int> map = new Dictionary<int, int>();//记录在每站上车或者下车的人数

        int len = trips.Length;
        int end = 0;//记录终点的车站
        for (int i = 0; i < len; i++)
        {
            
       end = Math.Max(end, trips[i][2]);
        }
        //计算差分数组
         int[] diff=new int[end+1];

       
        for (int i = 0; i < len; i++)//遍历所有的trip
        {
            diff[trips[i][1]] += trips[i][0];
            diff[trips[i][2]] -= trips[i][0];


        }
        int count = 0;
        for (int i = 0; i <= end; i++)//遍历所有的车站
        {
            count += diff[i];
            if(count > capacity)
            {
                return false ;
            }


        }

        return true;
    }
}
class program1094
{

    static void Main1094()
    {

        //string s;
        //while ((s = Console.ReadLine()) != null)
        //{

        //    string[] tokens = s.Split(' ');
        //    int[] nums = new int[tokens.Length];
        //    for (int i = 0; i < tokens.Length; i++)
        //    {
        //        nums[i] = int.Parse(tokens[i]);

        //    }


        //}
        Sol1094 sol1094
            = new Sol1094();
        int[][] trips = new int[2][];
        for (int i = 0; i < trips.Length; i++) {
            trips[i] = new int[3];
        }
        trips[0][0] = 2;
        trips[0][1] = 1;
        trips[0][2]      = 5;
        trips[1][0] = 3;
        trips[1][1] = 3;
        trips[1][2] = 7;

     bool res=   sol1094.CarPooling(trips, 4);
        Console.WriteLine(res);

    }
}